10.复杂数据处理 · 结构转换（下）

10.复杂数据处理 · 结构转换（下）

在上一节中，我们学习了如何实现一些简单数据结构的转换，在这一节中我们将继续学习更为复杂的数据格式之间的转换。

10.1 数据集

在上一节的最后，我们提到了两种用于存储表格数据的结构：行式数据集（Row-oriented Dataset）和列式数据集（Column-oriented Dataset）。这两种数据集在二维空间中都同样标识了一个矩阵式数据集，但它们存储的方式和适用的范围不一样。

例如，以下这个数据集存储了某公司的一部分人员信息。该数据集包含了五个数据列和五个数据行，其中每一行代表了一个员工的信息，而每一列对应的则是不同的信息维度。

RowId

EmpId

Lastname

Firstname

Salary

001

10

Smith

Joe

40000

002

12

Jones

Mary

50000

003

11

Johnson

Cathy

44000

004

22

Jones

Bob

55000

005

24

Steve

Mike

62000

如果将这个数据集分别使用行式数据集和列式数据集两种数据结构进行存储的话，则将会是以下形式的实际结构。

行式数据集

// Row-oriented Dataset
const empsRows = [
  { RowId: '001', EmpId: '10', Lastname: 'Smith', Firstname: 'Joe', Salary: 40000 },
  { RowId: '002', EmpId: '12', Lastname: 'Jones', Firstname: 'Mary', Salary: 50000 },
  { RowId: '003', EmpId: '11', Lastname: 'Johnson', Firstname: 'Cathy', Salary: 44000 },
  { RowId: '004', EmpId: '22', Lastname: 'Jones', Firstname: 'Bob', Salary: 55000 },
  { RowId: '005', EmpId: '24', Lastname: 'Steve', Firstname: 'Mike', Salary: 62000 }
]

列式数据集

// Column-oriented Dataset
const empsColumns = {
  RowId: [ '001', '002', '003', '004', '005' ],
  EmpId: [ '10', '12', '11', '22', '24' ],
  Lastname: [ 'Smith', 'Jones', 'Johnson', 'Jones', 'Steve' ],
  Firstname: [ 'Joe', 'Mary', 'Cathy', 'Bob', 'Mike' ],
  Salary: [ 40000, 50000, 44000, 55000, 62000 ]
}

这两种数据集存储结构各有其不同的优势和优化方式，在数据库领域中有分别基于这两种结构实现的不同数据库软件，如基于行式的 MySQL (opens new window) 以及基于列式的 Apache HBase (opens new window)。行式数据集有直观、单一行内的数据结构稳定、利于行式切分存储等优点，而列式数据集的好处是可以通过忽略非必要列以加速数据读取、查询等操作。甚至有些框架或者语言中的数据集就是以列式进行存储的，比如在广泛用于统计领域的 R 语言中的数据框 data.frame，其中的每一列都是以一个向量 vector 进行存储的。

当然讨论数据库和其他语言并不在本小册的范围，所以还是让我们回到正题上来。事实上我们在很多的数据 API 中都会发现，API 所提供的数据结构基本上都是以行式数据提供的。这是因为后端服务所使用的大部分都是行式数据库，再者行式数据在后端程序的处理中也更为方便直接。

10.1.1 为什么要使用列式数据集

为什么在前端我们还要使用到这两种数据结构呢，或者说在前端开发中，列式数据集又有哪些应用场景呢？我们再次将目光放回到上面这张员工数据集上，如果要统计数据集中各员工的收入水平，我们可以选用最大公约数（）再乘以 10 作为约数，然后进行取整的结果作为统计区间。

然而这里我们只需要用到数据集中的 Salary 这一个字段，如果该数据集的尺寸远比 大的话，使用整个数据集进行计算显然会浪费非常多的计算资源（CPU 时间、内存空间、IO 等）。这时候列式数据集的优势便体现出来了，只取该一列的数据进行计算即可。

function gcd(a, b) {
  if (b === 0) {
    return a
  }
  
  return gcd(b, a % b)
}

const w = empsColumns.Salary.reduce(gcd) * 10
const W = empsColumns.Salary
  .map(function(s) {
    return Math.floor(s / w)
  })

console.log(W) //=> [4, 5, 4, 5, 6]

得到了各数据所落到的区间后，再进行统计，最后得到的结果便可用于图表绘制了。同样，我们可以使用前面编写的 _.reduceByKey 进行统计计算。

const salaryAnalysis = _.reduceByKey(
  W.map(function(W_i) {
    return [ W_i, 1 ]
  }),
  function(a, b) {
    return a + b
  }
)

console.log(salaryAnalysis)
//=> [
//   ["4", 2],
//   ["5", 2],
//   ["6", 1]
// ]

如果要找出不同收入层次的人的名字，需要使用到其他列的数据，那么在列式数据集中该如何使用呢？其实非常简单，无论是在 JavaScript 中的列式数据集还是基于列式的数据库，当需要使用到其他列的时候使用相同的下标即可。

const groupedNames = _.mapValues(
  _.groupBy(
    empsColumns.Salary
      .map(function(s) {
        return Math.floor(s / w)
      })
      .map(function(W_i, i) {
        return {
          w: W_i,
          name:`${empsColumns.Firstname[i]} ${empsColumns.Lastname[i]}`
        }
      }),
    'w'
  ),
  function(items) {
    return items.map(_.iteratee('name'))
  }
)

console.log(groupedNames)
//=> {
//   4: [ "Joe Smith", "Cathy Johnson" ],
//   5: [ "Mary Jones", "Bob Jones" ],
//   6: [ "Mike Steve" ]
// }

10.1.2 行式数据集 → 列式数据集

了解完列式数据集的好处和实际使用方式之后，我们来学习下如何将前端生成或者从后端服务中取得的行式数据集转换为列式数据集。

首先我们要了解数据集并不一定是完全密集的，也就是说某些字段是允许为空的，在以对象字面量作为一行的行式数据集中便有某一个字段不存在或为 null/undefined。同样，在列式数据集中也可以使用 null 或 undefined 来表示空字段。

假设我们并不知道某个行式数据集究竟有哪些字段列，因为很有可能前面所有的数据行中都不存在的某个字段，在最后一行出现了。而且在实际业务开发中很有可能数据并非一次性加载完成，而是通过数据流的形式不断添加的。因此我们需要能够随时检查是否有新字段列产生，如果有，将其添加到目标列式数据集中。

首先定义一个用于初始化列式数据集中新字段的函数，逻辑很简单，检查目标数据集中是否已经存在目标字段，如果不存在将其初始化为一个空数组。

function applyColumn(colDataset, columnName) {
  if (!_.has(colDataset, columnName)) {
    colDataset[columnName] = []
  }

  return colDataset
}

然后将行式数据集中的每一个对象字面量所包含的字段都插入到对应行列位置上即可。

function rowOriented2ColOriented(rowDataset) {
  let colDataset = {}

  rowDataset.forEach(function(row, i) {
    const columnNames = _.keys(row)

    columnNames.forEach(function(columnName) {
      colDataset = applyColumn(colDataset, columnName)
      colDataset[columnName][i] = row[columnName]
    })
  })

  return colDataset
}

const transformedDataset = rowOriented2ColOriented(empsRows)

console.log(transformedDataset)
//=> {
//  RowId: [ '001', '002', '003', '004', '005' ],
//  EmpId: [ '10', '12', '11', '22', '24' ],
//  Lastname: [ 'Smith', 'Jones', 'Johnson', 'Jones', 'Steve' ],
//  Firstname: [ 'Joe', 'Mary', 'Cathy', 'Bob', 'Mike' ],
//  Salary: [ 40000, 50000, 44000, 55000, 62000 ]
// }

10.1.3 列式数据集 → 行式数据集

当需求变成将列式数据集转换为行式数据集时，需要考虑的技术点也会相应地发生改变。在行式转列式的过程中需要注意的是未知字段列的添加，而列式转行式时则需要注意跳过空字段。

而且因为列式数据集是必须带有顺序的，所以很有可能会出现当前最后一行数据并不是完整的数据，即所有的字段列的长度并不一定相等。

因此在开始遍历每一个字段列之前，需要先检查该数据集究竟有多少个数据行，方法也很简单，就是找出最长的那个字段列。

function rowOriented2ColOriented(colDataset) {
  const columnNames = _.keys(colDataset)

  const n = _.max(columnNames.map(function(colName) {
    return colDataset[colName].length
  }))

  const rowDataset = []

  for (let i = 0; i < n; ++i) {
    const row = {}

    columnNames.forEach(function(colName) {
      if (!_.isNil(colDataset[colName][i])) {
        row[colName] = colDataset[colName][i]
      }
    })

    rowDataset[i] = row
  }

  return rowDataset
}

const empsRows = rowOriented2ColOriented(empsColumns)

console.log(empsRows)
//=> [
//   { RowId: '001', EmpId: '10', Lastname: 'Smith', Firstname: 'Joe', Salary: 40000 },
//   { RowId: '002', EmpId: '12', Lastname: 'Jones', Firstname: 'Mary', Salary: 50000 },
//   { RowId: '003', EmpId: '11', Lastname: 'Johnson', Firstname: 'Cathy', Salary: 44000 },
//   { RowId: '004', EmpId: '22', Lastname: 'Jones', Firstname: 'Bob', Salary: 55000 },
//   { RowId: '005', EmpId: '24', Lastname: 'Steve', Firstname: 'Mike', Salary: 62000 }
// ]

10.2 序列集 & 树形结构 & 关系图谱

假设我们有这样一个数据表，它存储着一些有序序列，比如像下面这种的。

使用 JavaScript 中的数组进行表达的话，它可能会是这样的。

const sequences = [
  [ 'A', 'B', 'C' ],
  [ 'B', 'C', 'D' ],
  [ 'B', 'D', 'E' ],
  [ 'B', 'F', 'G' ],
  [ 'F', 'G', 'H' ],
  [ 'F', 'G', 'H', 'I' ],
  [ 'J', 'G' ],
  [ 'J', 'G', 'H' ],
  [ 'J', 'G', 'H', 'I' ]
]

这种数据结构常用于一些事件流程、关系网络等，因为在后端数据库中通常只能用这种形式存储事物之间的联系，而很难直接存储一张关系图谱或者树形结构，但实际业务开发中又需要使用真正的关系图谱或树形结构，所以我们需要懂得如何将离散存储的关系对或关系序列转换为所需要的数据结构。

10.2.1 序列集 → 树形结构

当我们将一系列有序序列整合成一个或多个树形结构时，需要注意以下几点：

1. 每个序列的不同首端是否都为独立的根节点；
2. 节点是否可重复；
3. 序列中是否允许存在回环；
4. 每个序列的末端是否都为独立的叶节点。

每个序列的不同首端是否都为独立的根节点

每个序列的不同首端是否都为独立的根节点，会直接影响到转换所得的树形结构的数量，我们以下图来理解每个互不相同的首端是与不是独立根节点的区别。

节点是否可重复

节点是否可重复决定了，转换的目标数据结构究竟是树形结构还是一个关系图谱，当多个序列中出现相同的节点时，因为顺序的关系它们并不处于同一个分支中，就会变成多个分支中有着相同的节点。

序列中是否允许存在回环

当序列集中允许出现重复节点时，很可能会出现同一个序列中有着重复的节点，从而形成回环。而在树形结构中，一旦出现回环树形结构便会变为更为立体的关系图谱结构。

每个序列的末端是否都为独立的叶节点

在树形结构中叶节点的定义为树形结构中没有子节点的节点，但是在序列集转换为树形结构时会产生特殊的情况。当序列 的节点为序列 的前半部分，序列 较序列 的后端多出一个或多个节点时，如果序列 的末端节点被定义为一个独立的叶节点，那么在构建树形结构时如何界定，一个分支中的中间节点（如序列 的末端节点）是原本序列集中的一个叶节点呢？这也是后面我们将要讨论的内容。

1. 各首端为独立根节点

当我们所需要转换的序列集中，每一个不同的首端都为独立的根节点时，就意味着不同的首端会成为一个独立的树形结构，从而转换为一个包含多个树形结构的“森林”。

比如本节开头的有序序列集，其中就包含了 4 个不同的首端：A、B、F 和 J。那么这个序列集就可以转换为这样的一个“森林”。

这种情况下，我们可以使用一个虚拟的根节点来完成每一个序列的转换：

1. 创建一个虚拟的根节点，所有的实际根节点都以它为父节点；
2. 遍历序列中的每一个节点；
3. 从虚拟的根节点作为父节点开始，检查父节点是否包含序列中当前的节点，若不存在则往父节点中添加当前节点；
4. 以最新的节点作为父节点，遍历到序列中的下一个节点并重复步骤 3，直至当前序列的末端。

我们可以利用下面这张图来更好地理解这个转换算法。

配合第 7 节中我们所使用的树形结构代码，来完成这个转换算法，然后使用 Node.toString() 将其展示出来以确认是否成功并正确地完成转换。

// 虚拟一个根节点
const root = new Node('*')

sequences.forEach(function(sequence) {
  let lastNode = root
  
  sequence.forEach(function(nodeName, i) {
    // 寻找已存在的节点
    const index = lastNode.children.findIndex(function(child) {
      return child.name === nodeName
    })

    if (index >= 0) {
      lastNode = lastNode.children[index]
    } else {
      // 创建节点
      const node = new Node(nodeName)

      lastNode.addChild(node)

      lastNode = node
    }
  })
})

console.log(root.toString())
//=>
// *
//   A
//     B
//       C
//   B
//     C
//       D
//     D
//       E
//     F
//       G
//   F
//     G
//       H
//         I
//   J
//     G
//       H
//         I

2. 各首端不为独立根节点

当序列集中的各首端并不为独立根节点时，整个序列集所转换成的树形结构数量会大大减少，甚至整个序列集都会以一棵树形结构呈现。

可以看到，在这个转换得到了两个树形结构，分别为以节点 A 和节点 J 为根节点。进行转换之前我们需要知道的是，序列集很有可能是无序的，也就是说，并非序列集中第一个序列的第一个节点必定是一个根节点。

因此，在转换的过程中需要完成的第一步便是寻找序列集中，既定存在的若干个根节点。回想一下我们在第 7 节和第 8 节中学过的内容，一般来说，如何辨别树形结构和关系图谱中的节点究竟是根节点、中间节点还是叶节点的？

根节点的定义是：没有父节点的节点。那么换过来说，如果要寻找序列集中的根节点，第一步便是对其中的所有节点进行整理统计，最直观的办法是将每个序列拆分成多个节点对，即父节点和子节点的配对关系。

针对上面 sequences 这种形式的序列集，我们可以通过遍历序列中除了最后一个节点以外的所有节点，并返回与其下一个元素所组成的元组，以表达树形结构中的父子节点关系。

function isLast(i, length) {
  return (i + 1) === length
}

function seq2Pairs(seq) {
  return seq
    .map(function(node, i) {
      if (isLast(i, seq.length)) {
        return false
      }

      return [ node, seq[i + 1] ]
    })
    .filter(function(pair) {
      return pair && pair.length === 2
    })
}

const pairs = seq2Pairs([ 'A', 'B', 'C' ])

console.log(pairs)
//=> [
//   ["A", "B"],
//   ["B", "C"]
// ]

得到了一系列的父子对之后，我们便可以分别统计每一个出现的节点各自的入度和出度，以找出根节点集并提前向虚拟根节点插入这些根节点。

// 统计节点的度
function analyzeDegrees(pairs) {
  const analysis = {}

  for (const pair of pairs) {
    const [ left, right ] = pair

    if (!analysis[left]) {
      analysis[left] = {
        in: 0, out: 0
      }
    }
    if (!analysis[right]) {
      analysis[right] = {
        in: 0, out: 0
      }
    }

    analysis[left].out += 1
    analysis[right].in += 1
  }

  return _.toPairs(analysis)
    .map(function([ node, degrees ]) {
      return { node, ...degrees }
    })
}

// 通过判断入度找出根节点
function findRootNodes(analysis) {
  return analysis.filter(function({ in: inDegree }) {
    return inDegree === 0
  })
}

const analysis = analyzeDegrees(pairs)
const rootNodes = findRootNodes(analysis).map(function(result) {
  return result.node
})

console.log(rootNodes)
//=> [ 'A' ]

const root = new Node('*')

for (const nodeName of rootNodes) {
  const node = new Node(nodeName)

  root.addChild(node)
}

接下来的处理其实跟序列各首端为独立根节点时很相似，不过有一点区别：在前面的情况中，每一个序列的首端都必定会出现在虚拟根节点的子节点中，因此可以直接从根节点开始操作，而在现在的条件下，每个序列的首端节点并不一定是虚拟根节点的子节点，因此除了一个虚拟根节点以外还需要建立使用第 7 节中的树型结构，并使用 Tree.search() 方法来完成上层节点的搜索。

const tree = new Tree(root)

// 任务队列
const penddingSeqs = sequences.slice()

while (penddingSeqs.length > 0) {
  const currentSeq = penddingSeqs.shift()

  // 搜索首端节点
  const hit = tree.search(function(node) {
    return node.name === currentSeq[0]
  }).shift()

  // 如果不存在，则将当前序列重新加入任务队列
  if (!hit) {
    penddingSeqs.push(currentSeq)
    continue
  }

  let lastNode = hit
  currentSeq.shift()

  while (currentSeq.length > 0) {
    const currentNodeName = currentSeq.shift()

    const currentNode = lastNode.children.find(function(node) {
      return node.name === currentNodeName
    })

    if (currentNode) {
      lastNode = currentNode
    } else {
      const node = new Node(currentNodeName)
      lastNode.addChild(node)

      lastNode = node
    }
  }
}

console.log(root.toString())
//=>
// *
//   A
//     B
//       C
//         D
//       D
//         E
//       F
//         G
//           H
//             I
//   J
//     G
//       H
//         I

10.2.2 序列集 → 关系图谱

与树形结构相比，将序列集转换为关系图谱的方法要简单许多。在第 8 节中我们曾说到，关系图谱的存储方式一般会由一个顶点集和一个边集组成，而序列集从数据结构上可以看做是一个更高维度的边集。因此，我们如果需要将序列集转换为关系图谱，只需要将序列集中的所有独立节点提取出来，然后将序列拆分成有向边或无向边并完成去重即可。

可以参考上面提取序列集中父子对的过程，此处不再演示代码，这个任务由你来完成。

小结

本节中我们学习了多种复杂数据结构之间的转换，其中也包括了上一节中我们所留下的两种数据集结构之间的转换。

这些数据结构在我们日常的开发中都是非常常见的，而且由于数据存储格式的限制或数据传输的约束，我们往往需要通过另一种方式来存储难以表达的数据结构，如序列集与树形结构、关系图谱的关系。

习题

1. 参考 10.2.1 节中第 2 小节里的转换算法，完成序列集到关系图谱的转换。
2. 思考：树形结构作为特殊的关系图谱，我们如何将其一般化，转换为关系图谱呢？